function Graph(v) {
    this.vertices = v;
    this.edges = 0;
    this.adj = [];
    this.marked = [];
    this.edgeTo = [];
    for(var i = 0; i < this.vertices; i++) {
        this.marked[i] = false;
    }
    for(var i = 0; i < this.vertices; i++) {
        this.adj[i] = [];
    }
}
Graph.prototype.addEdge = function(v, w) {
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.edges++;
}
Graph.prototype.showGraph = function() {
    for(var i = 0; i < this.vertices; i++) {
        console.log(i + '->');
        for(var j = 0; j < this.adj[i].length; j++) {
            console.log(this.adj[i][j] + ' ');
        }
    }
}
Graph.prototype.dfs = function(v) {
    this.marked[v] = true;
    if(this.adj[v] !== undefined) {
        console.log('visit vertex:', v, this.adj[v]);
        for(var i = 0; i < this.adj[v].length; i ++) {
            if(!this.marked[this.adj[v][i]]) {
                this.dfs(this.adj[v][i]);
            }
        }
    }
}
Graph.prototype.bfs = function(s) {
    var queue = [];
    this.marked[s] = true;
    queue.push(s);
    while(queue.length > 0) {
        var v = queue.shift();
        if(v !== undefined) {
            console.log('visited:', v);
        }
        for(var i = 0; i < this.adj[v].length; i++) {
            var w = this.adj[v][i];
            if(!this.marked[w]) {
                this.edgeTo[w] = v;
                this.marked[w] = true;
                queue.push(w);
            }
        }
        console.log('queue:', queue);
    }
    console.log('edgeTo:', this.edgeTo);
}

Graph.prototype.pathTo = function(v) {
    var source = 0;
    if(!this.hasPathTo(v)) {
        return undefined;
    }
    var path = [];
    for(var i = v; i != source; i = this.edgeTo[i]) {
        path.push(i);
    }
    path.push(source);
    return path;
}

Graph.prototype.hasPathTo = function(v) {
    return this.marked[v];
}

g = new Graph(6);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.addEdge(3,4);
g.addEdge(3,5);
g.addEdge(4,5);

g.showGraph();
// g.dfs(0);
g.bfs(0);
var vertex = 5;
var paths = g.pathTo(vertex);
console.log(paths);